|
The Euler tour technique (ETT), named after Leonhard Euler, is a method in graph theory for representing trees. The tree is viewed as a directed graph that contains two directed edges for each edge in the tree. The tree can then be represented as a Eulerian circuit of the directed graph, known as the Euler tour representation (ETR) of the tree. The ETT allows for efficient, parallel computation of solutions to common problems in algorithmic graph theory. It was introduced by Tarjan and Vishkin in 1984. ==Construction== Given an undirected tree presented as a set of edges, the Euler tour representation (ETR) can be constructed in parallel as follows: * We construct a symmetric list of directed edges: * * For each undirected edge in the tree, insert (''u'',''v'') and (''v'',''u'') in the edge list. * Sort the edge list lexicographically. (Here we assume that the nodes of the tree are ordered, and that the root is the first element in this order.) * Construct adjacency lists for each node (called ''next'') and a map from nodes to the first entries of the adjacency lists (called ''first''): * * For each edge (''u'',''v'') in the list, do in parallel: * * * If the previous edge (''x'',''y'') has ''x'' ≠ ''u'', i.e. starts from a different node, set first(''u'') = (''u'',''v'') * * * Else if ''x'' = ''u'', i.e. starts from the same node, set next(''x'',''y'') = (''u'',''v'') Construct an edge list (called ''succ'') in Euler tour order by setting pointers succ(''u'',''v'') for all edges (''u'',''v'') in parallel according to the following rule: : The resulting list ''succ'' will be circular. The overall construction takes work ''W''(''n'') = O(sort(''n'')) (the time it takes to sort ''n'' items in parallel) if the tree has ''n'' nodes, as in trees the number of edges is one less than the number of nodes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Euler tour technique」の詳細全文を読む スポンサード リンク
|